import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;


public class Leetcode524 {
    public static void main(String[] args) {
        int res[][] = updateMatrix(new int[][]{
                {0, 0, 0},
                {0, 1, 0},
                {1, 1, 1},
        });
        for (int k[] : res) {
            System.out.println(Arrays.toString(k));
        }
    }

    private static final Index LEFT = new Index(-1, 0);
    private static final Index RIGHT = new Index(1, 0);
    private static final Index UP = new Index(0, -1);
    private static final Index DOWN = new Index(0, 1);

    private static final Index[] NEIGHBORS = {LEFT, RIGHT, UP, DOWN};

    public static int[][] updateMatrix(int[][] mat) {
        int[][] res = new int[mat.length][mat[0].length];

        Queue<Index> queue = new LinkedList<>();

        boolean[][] isHandle = new boolean[mat.length][mat[0].length];

        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[i].length; j++) {
                if (mat[i][j] == 0) {
                    queue.offer(new Index(i, j));
                    res[i][j] = 0;
                    isHandle[i][j] = true;
                } else {
                    res[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        while (!queue.isEmpty()) {
            Index index = queue.poll();

            for (Index neighbor : NEIGHBORS) {
                Index exist = neighbor.add(index);

                if (exist.x < 0 || exist.x >= res.length || exist.y < 0 || exist.y >= res[exist.x].length) {
                    continue;
                }

                if (isHandle[exist.x][exist.y]) {
                    continue;
                }

                if (res[index.x][index.y] + 1 < res[exist.x][exist.y]) {
                    res[exist.x][exist.y] = res[index.x][index.y] + 1;
                    queue.offer(exist);
                    isHandle[exist.x][exist.y] = true;
                }
            }

        }

        return res;
    }

    static class Index {
        int x;
        int y;

        public Index(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public Index add(Index index) {
            return new Index(index.x + this.x, index.y + this.y);
        }
    }

}
